package hash

import (
	"gitee.com/kklt1996/data-structure/tree"
	"hash/fnv"
	"strconv"
)

/**
扩容素数表
*/
var capacityPrime = []int{17, 31, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
	49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
	12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741}

/*
	哈希表的实现
*/
type Table struct {
	/*
		哈希表
	*/
	hashtable []*tree.RedBlackTree
	/*
		模的大小(数组容量的大小)
	*/
	capacity int
	/*
	 元素的个数
	*/
	size int

	/*
		平均每隔地址承载的元素上限
	*/
	upperTol int

	/*
		平均每个地址承载的元素个数下线
	*/
	lowerTol int

	comparator func(thisKey interface{}, compareKey interface{}) int

	capacityIndex int
}

func (table Table) GetSize() int {
	return table.size
}

/*
	添加或者修改某个key对应的value
	key 如果不是int float64 string 类型，那么必须实现hash.Able接口
*/
func (table *Table) Put(key interface{}, value interface{}) {
	hash := table.hash(key)
	redBlackTree := table.hashtable[hash]
	if redBlackTree.Contains(key) {
		redBlackTree.Add(key, value)
	} else {
		// 之前不存在需要size++
		table.size++
		redBlackTree.Add(key, value)
		// 每个哈希地址所容纳的元素个数大于最大允许值
		if table.size > table.capacity*table.upperTol && table.capacityIndex < (len(capacityPrime)-1) {
			table.capacityIndex++
			table.resize(capacityPrime[table.capacityIndex])
		}
	}
}

/*
	删除某个key
*/
func (table *Table) Remove(key interface{}) interface{} {
	hash := table.hash(key)
	redBlackTree := table.hashtable[hash]
	contains := redBlackTree.Contains(key)
	if contains {
		element, _ := redBlackTree.RemoveElement(key)
		table.size--
		// 每个哈希地址所容纳的元素个数小于最小允许值
		if table.size < table.capacity*table.lowerTol && table.capacityIndex > 0 {
			table.capacityIndex--
			table.resize(capacityPrime[table.capacityIndex])
		}
		return element
	}
	return nil
}

/*
	查询是否包含某个key
*/
func (table Table) Contains(key interface{}) bool {
	return table.hashtable[table.hash(key)].Contains(key)
}

/*
	查询某个key对应的value
*/
func (table Table) Get(key interface{}) interface{} {
	return table.hashtable[table.hash(key)].Get(key)
}

/*
	进行容量的变更
*/
func (table *Table) resize(newCapacity int) {
	// 创建新的哈希表
	newHashTable := make([]*tree.RedBlackTree, newCapacity, newCapacity)
	for i := 0; i < newCapacity; i++ {
		newHashTable[i] = tree.CreateRedBlackTree(table.comparator)
	}

	// 重新分配元素所在位置
	oldCapacity := table.capacity
	table.capacity = newCapacity
	for i := 0; i < oldCapacity; i++ {
		redBlackTree := table.hashtable[i]
		redBlackTree.InOrder(func(key interface{}, value interface{}) bool {
			newHashTable[table.hash(key)].Add(key, value)
			return false
		})
	}
	table.hashtable = newHashTable
}

func (table Table) hash(key interface{}) int {
	switch key.(type) {
	case int:
		key = strconv.Itoa(key.(int))
	case float64:
		key = strconv.FormatFloat(key.(float64), 'f', 6, 64)
	case string:
	default:
		// 不是以上类型必须实现了HashCode() 方法
		key = key.(Able).HashCode()
	}
	h := fnv.New32a()
	_, _ = h.Write([]byte(key.(string)))
	return (int(h.Sum32()) & 0x7fffffff) % table.capacity
}
